/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package arbre;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author Xuan Huy
 */
public class ArbreRougeNoir extends ArbreRecherche {

    private static Noeud sentinelle = new Noeud(0, Couleur.NOIR);

    /**
     * @see ArbreRecherche#ArbreRecherche().
     */
    public ArbreRougeNoir() {
        super();
        initialiserFeuilles();
    }

    /**
     * @see ArbreRecherche#ArbreRecherche(arbre.Noeud).
     * @param racine
     */
    public ArbreRougeNoir(Noeud racine) {
        super(racine);
        racine.setParent(sentinelle);
        initialiserFeuilles();
    }

    /**
     * La méthode effectue une rotation à gauche sur le noeud
     * <code>noeud</code>, tout en préservant la propriété d'un arbre binaire de
     * recherche.
     *
     * @param noeud le noeud sur lequel est effectuée la rotation.
     * @see ArbreRougeNoir#rotationDroite(arbre.Noeud).
     */
    public void rotationGauche(Noeud noeud) {
        Noeud y = noeud.getDroite();
        noeud.setDroite(y.getGauche());
        if (y.getGauche() != sentinelle) {
            y.getGauche().setParent(noeud);
        }
        y.setParent(noeud.getParent());
        if (noeud.getParent() == sentinelle) {
            racine = y;
        } else if (noeud == noeud.getParent().getGauche()) {
            noeud.getParent().setGauche(y);
        } else {
            noeud.getParent().setDroite(y);
        }
        y.setGauche(noeud);
        noeud.setParent(y);
    }

    /**
     * La méthode effectue une rotation à droite sur le noeud
     * <code>noeud</code>, tout en préservant la propriété d'un arbre binaire de
     * recherche.
     *
     * @param noeud le noeud sur lequel est effectuée la rotation.
     * @see ArbreRougeNoir#rotationGauche(arbre.Noeud).
     */
    public void rotationDroite(Noeud noeud) {
        Noeud y = noeud.getGauche();
        noeud.setGauche(y.getDroite());
        if (y.getDroite() != sentinelle) {
            y.getDroite().setParent(noeud);
        }
        y.setParent(noeud.getParent());
        if (noeud.getParent() == sentinelle) {
            racine = y;
        } else if (noeud == noeud.getParent().getGauche()) {
            noeud.getParent().setGauche(y);
        } else {
            noeud.getParent().setDroite(y);
        }
        y.setDroite(noeud);
        noeud.setParent(y);
    }

    /**
     * @see ArbreRecherche#getFeuilles().
     */
    @Override
    public List<Noeud> getFeuilles() {
        return getFeuilles(racine);
    }

    /**
     * @see ArbreRecherche#getFeuilles(arbre.Noeud).
     */
    public static List<Noeud> getFeuilles(Noeud noeud) {
        /**
         * Remplacer les références à
         * <code>null</code> par
         * <code>sentinelle</code>.
         */
        List<Noeud> feuilles = new ArrayList<>();
        if (noeud.getGauche() == sentinelle && noeud.getDroite() == sentinelle) {
            feuilles.add(noeud);
        } else {
            if (noeud.getGauche() != sentinelle) {
                feuilles.addAll(getFeuilles(noeud.getGauche()));
            }
            if (noeud.getDroite() != sentinelle) {
                feuilles.addAll(getFeuilles(noeud.getDroite()));
            }
        }
        return feuilles;
    }

    /**
     * La méthode calcule et retourne la hauteur noire de l'arbre rouge-noir
     * enraciné par le noeud
     * <code>noeud</code>.
     *
     * @param noeud le noeud racine de l'arbre dont on veut calculer la hauteur
     * noire.
     * @return la hauteur noire de <code>noeud</code>.
     */
    public static int getHauteurNoire(Noeud noeud) {
        int hauteurNoire = 0;
        Noeud gauche = noeud.getGauche();
        Noeud droite = noeud.getDroite();
        if (gauche != sentinelle) {
            hauteurNoire = getHauteurNoire(gauche) + 1;
        } else if (droite != sentinelle) {
            hauteurNoire = getHauteurNoire(droite) + 1;
        }
        return hauteurNoire;
    }

    /**
     * La méthode calcule et retourne la hauteur noire de l'arbre rouge-noir
     * actuel.
     *
     * @return la hauteur noire de l'arbre rouge-noir actuel.
     */
    public int getHauteurNoire() {
        return getHauteurNoire(racine);
    }

    /**
     * La méthode insère le noeud
     * <code>noeud</code> dans l'arbre actuel, tout en conservant les
     * contraintes d'un arbre binaire de recherche et les propriétés d'un arbre
     * rouge-noir. Le noeud inséré sera colorié en rouge.
     *
     * @param noeud le noeud à insérer.
     */
    @Override
    public void inserer(Noeud noeud) {
        Noeud y = sentinelle;
        Noeud x = racine;
        while (x != sentinelle) {
            y = x;
            if (noeud.getCle() < x.getCle()) {
                x = x.getGauche();
            } else {
                x = x.getDroite();
            }
        }
        noeud.setParent(y);
        if (y == sentinelle) {
            racine = noeud;
        } else {
            if (noeud.getCle() < y.getCle()) {
                y.setGauche(noeud);
            } else {
                y.setDroite(noeud);
            }
        }
        noeud.setGauche(sentinelle);
        noeud.setDroite(sentinelle);
        noeud.setCouleur(Couleur.ROUGE);
        corrigerInsertion(noeud);
    }

    /**
     * La méthode supprime le noeud
     * <code>noeud</code> de l'arbre actuel, tout en conservant les contraintes
     * d'un arbre binaire de recherche et d'un arbre rouge-noir.
     *
     * @param noeud le noeud à supprimer.
     * @return le noeud détaché.
     */
    @Override
    public Noeud supprimer(Noeud noeud) {
        Noeud x, noeudDetache;
        if (noeud.getGauche() == sentinelle || noeud.getDroite() == sentinelle) {
            noeudDetache = noeud;
        } else {
            noeudDetache = successeur(noeud);
        }
        if (noeudDetache.getGauche() != sentinelle) {
            x = noeudDetache.getGauche();
        } else {
            x = noeudDetache.getDroite();
        }
        x.setParent(noeudDetache.getParent());
        if (noeudDetache.getParent() == sentinelle) {
            racine = x;
        } else if (noeudDetache == noeudDetache.getParent().getGauche()) {
            noeudDetache.getParent().setGauche(x);
        } else {
            noeudDetache.getParent().setDroite(x);
        }
        if (noeudDetache != noeud) {
            noeud.setCle(noeudDetache.getCle());
        }
        if (noeudDetache.getCouleur() == Couleur.NOIR) {
            corrigerSuppression(x);
        }
        return noeudDetache;
    }

    /**
     * Après avoir inséré un noeud dans l'arbre rouge-noir, certaines de ses
     * propriétes sont enfreintes. Cette méthode corrige les propriétés violées
     * à l'issue d'une insertion.
     *
     * @param noeud un noeud rouge.
     */
    protected void corrigerInsertion(Noeud noeud) {
        Noeud parent = noeud.getParent();
        while (parent.getCouleur() == Couleur.ROUGE) {
            /**
             * Comme le noeud parent est rouge, le noeud grand-parent s'il
             * existe est forcément noir. Le cas où le noeud parent est noir
             * n'est pas intéressant car il n'y aurait pas de violations des
             * propriétés d'un arbre rouge-noir, sachant que
             * <code>noeud</code> est toujours rouge.
             */
            if (parent == parent.getParent().getGauche()) {
                /**
                 * On récupère le noeud oncle du noeud
                 * <code>noeud</code>. On est dans le cas où
                 * <code>noeud</code> et son parent sont tous les deux rouges.
                 */
                Noeud oncle = parent.getParent().getDroite();
                if (oncle.getCouleur() == Couleur.ROUGE) {
                    /**
                     * Si le noeuds oncle, parent et
                     * <code>noeud</code> sont tous les trois rouges, on colorie
                     * les noeuds oncle et parent en noir, puis le noeud
                     * grand-parent en rouge pour assurer la propriété de la
                     * hauteur noire. Problème résolu pour
                     * <code>noeud</code> et son parent. Par contre, la
                     * recoloriage en rouge du noeud grand-parent peut
                     * introduire un nouveau conflit. A la fin,
                     * <code>noeud</code> prend la valeur de son noeud
                     * grand-parent et on recommence la boucle pour résoudre un
                     * éventuel conflit du fait que le noeud grand-parent est
                     * rouge.
                     */
                    parent.setCouleur(Couleur.NOIR);
                    oncle.setCouleur(Couleur.NOIR);
                    parent.getParent().setCouleur(Couleur.ROUGE);
                    noeud = parent.getParent();
                } else {
                    /**
                     * On est dans le cas où le noeud oncle est noir.
                     */
                    if (noeud == parent.getDroite()) {
                        /**
                         * Si
                         * <code>noeud</code> est l'enfant droite de son parent,
                         * on fait une rotation à gauche pour ramener au cas 3.
                         * Pour cela
                         * <code>noeud</code> prend temporairement la valeur de
                         * son noeud parent.
                         */
                        noeud = parent;
                        parent = noeud.getDroite();
                        rotationGauche(noeud);
                        /**
                         * Après la rotation à gauche,
                         * <code>noeud</code> redevient le noeud enfant.
                         */
                    }
                    /**
                     * Cas 3 : le noeud oncle est noir et
                     * <code>noeud</code> est l'enfant gauche de son parent. On
                     * colorie le noeud parent en noir, le noeud grand-parent en
                     * rouge et fait une rotation à droite pour garantir la
                     * propriété de la hauteur noire.
                     */
                    parent.setCouleur(Couleur.NOIR);
                    parent.getParent().setCouleur(Couleur.ROUGE);
                    rotationDroite(parent.getParent());
                }
            } else {
                Noeud oncle = parent.getParent().getGauche();
                if (oncle.getCouleur() == Couleur.ROUGE) {
                    parent.setCouleur(Couleur.NOIR);
                    oncle.setCouleur(Couleur.NOIR);
                    parent.getParent().setCouleur(Couleur.ROUGE);
                    noeud = parent.getParent();
                } else {
                    if (noeud == parent.getGauche()) {
                        noeud = parent;
                        parent = noeud.getGauche();
                        rotationDroite(noeud);
                    }
                    parent.setCouleur(Couleur.NOIR);
                    parent.getParent().setCouleur(Couleur.ROUGE);
                    rotationGauche(parent.getParent());
                }
            }
        }
        racine.setCouleur(Couleur.NOIR);
    }

    /**
     * Après avoir supprimé un noeud de l'arbre rouge-noir, certaines de ses
     * propriétes sont enfreintes. Cette méthode corrige les propriétés violées
     * à l'issue d'une suppression.
     *
     * @param noeud un noeud rouge ou noir.
     */
    protected void corrigerSuppression(Noeud noeud) {
        if (noeud != sentinelle) {
            while (noeud != racine && noeud.getCouleur() == Couleur.NOIR) {
                Noeud parent = noeud.getParent();
                if (noeud == parent.getGauche()) {
                    Noeud frere = parent.getDroite();
                    if (frere.getCouleur() == Couleur.ROUGE) {
                        frere.setCouleur(Couleur.NOIR);
                        parent.setCouleur(Couleur.ROUGE);
                        rotationGauche(parent);
                        frere = parent.getDroite();
                    }
                    if (frere.getGauche().getCouleur() == Couleur.NOIR
                            && frere.getDroite().getCouleur() == Couleur.NOIR) {
                        frere.setCouleur(Couleur.ROUGE);
                        noeud = parent;
                    } else {
                        if (frere.getDroite().getCouleur() == Couleur.NOIR) {
                            frere.getGauche().setCouleur(Couleur.NOIR);
                            frere.setCouleur(Couleur.ROUGE);
                            rotationDroite(frere);
                            frere = parent.getDroite();
                        }
                        frere.setCouleur(parent.getCouleur());
                        parent.setCouleur(Couleur.NOIR);
                        frere.getDroite().setCouleur(Couleur.NOIR);
                        rotationGauche(parent);
                        noeud = racine;
                    }
                } else {
                    Noeud frere = parent.getGauche();
                    if (frere.getCouleur() == Couleur.ROUGE) {
                        /**
                         * Cas 1 : le noeud frère est rouge, on recolorie les
                         * noeuds et fait une rotation à droite pour ramener aux
                         * cas 2, 3 ou 4.
                         */
                        frere.setCouleur(Couleur.NOIR);
                        parent.setCouleur(Couleur.ROUGE);
                        rotationDroite(parent);
                        frere = parent.getGauche();
                    }
                    if (frere.getGauche().getCouleur() == Couleur.NOIR
                            && frere.getDroite().getCouleur() == Couleur.NOIR) {
                        /**
                         * Cas 2 : le noeud frère est noir et ses deux enfants
                         * sont également noirs. On colorie le noeud frère en
                         * rouge et pousse le noir en trop du noeud
                         * <code>noeud</code> vers le noeud parent. Si on accède
                         * au cas 2 à partir du cas 1, la boucle se termine
                         * parce que le noeud parent qui était rouge se verra
                         * attribuer un noir supplémentaire, donc rouge
                         * finalement.
                         */
                        frere.setCouleur(Couleur.ROUGE);
                        noeud = parent;
                    } else {
                        /**
                         * Cas 3 : le noeud frère est noir, son enfant gauche
                         * est rouge, son enfant droite est noir. On recolorie
                         * les noeuds et fait une rotation à droite pour ramener
                         * au cas 4.
                         */
                        if (frere.getGauche().getCouleur() == Couleur.NOIR) {
                            frere.getDroite().setCouleur(Couleur.NOIR);
                            frere.setCouleur(Couleur.ROUGE);
                            rotationGauche(frere);
                            frere = parent.getGauche();
                        }
                        /**
                         * Cas 4 : le noeud frère est noir, son enfant droite
                         * est rouge, son enfant gauche est de couleur
                         * quelconque.
                         */
                        frere.setCouleur(parent.getCouleur());
                        parent.setCouleur(Couleur.NOIR);
                        frere.getGauche().setCouleur(Couleur.NOIR);
                        rotationDroite(parent);
                        noeud = racine;
                    }
                }
            }
            noeud.setCouleur(Couleur.NOIR);
        }
    }

    /**
     * La méthode initialise les noeuds feuilles en attribuant la sentinelle à
     * leurs enfants droites et gauches.
     */
    private void initialiserFeuilles() {
        List<Noeud> feuilles = super.getFeuilles();
        for (Noeud feuille : feuilles) {
            feuille.setGauche(sentinelle);
            feuille.setDroite(sentinelle);
        }
    }
}
